package offer;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

@FunctionalInterface
public interface SubArrayRanges {
    long subArrayRanges(int[] nums);
}

class SubArrayRangesTest{
    static final int[] TEST_01 = new int[]{1,2,3};

    public static void main(String[] args) {
        new SubArrayRangesImpl1().subArrayRanges(TEST_01);
    }


}
class SubArrayRangesImpl1 implements SubArrayRanges{
    /*
        抄的，o（n^2),o(1)
     */
    @Override
    public long subArrayRanges(int[] nums) {
        long ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int maxs = Integer.MIN_VALUE;
            int mins = Integer.MAX_VALUE;
            for (int j = i ; j < n; j++) {
                maxs = Math.max(maxs, nums[j]);
                mins = Math.min(mins, nums[j]);
                ans += maxs - mins;
            }
        }
        return ans;
    }
}

class SubArrayRangesImpl2 implements SubArrayRanges{
    /*
        动态规划o(n^2),o(n^2)
     */
    @Override
    public long subArrayRanges(int[] nums) {
        long ans = 0;
        int n = nums.length;
        int[][] intervalMax = new int[n][n];
        int[][] intervalMin = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(intervalMax[i], Integer.MIN_VALUE);
            Arrays.fill(intervalMin[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < n; i++) {
            intervalMax[i][i] = nums[i];
            intervalMin[i][i] = nums[i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                intervalMax[i][j] = Math.max(intervalMax[i][j - 1], nums[j]);
                intervalMin[i][j] = Math.min(intervalMin[i][j - 1], nums[j]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                ans += intervalMax[i][j] - intervalMin[i][j];
            }
        }

        return ans;
    }
}
class SubArrayRangesImpl3 implements SubArrayRanges{

    /*
        o(n),o(n),的单调栈实现，没看懂，抄了一份
     */
    @Override
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        int[] minLeft = new int[n];
        int[] minRight = new int[n];
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];

        Deque<Integer> minStack = new ArrayDeque<>();
        Deque<Integer> maxStack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while(!minStack.isEmpty() && nums[minStack.peek()] > nums[i]){
                minStack.pop();
            }
            minLeft[i] = minStack.isEmpty() ?  -1 : minStack.peek();
            minStack.push(i);

            while(!maxStack.isEmpty() && nums[maxStack.peek()] <= nums[i]){
                maxStack.pop();
            }
            maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
            maxStack.push(i);

        }
        minStack.clear();
        maxStack.clear();

        for (int i = 0; i < (n - 1); i++) {
            while(!minStack.isEmpty() && nums[maxStack.peek()] < nums[i]){
                maxStack.pop();
            }

            while(!maxStack.isEmpty() && nums[maxStack.peek()] < nums[i]){
                maxStack.pop();
            }
            maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
            maxStack.push(i);
        }

        long sumMax = 0, sumMin = 0;
        for (int i = 0; i < n; i++) {
            sumMax += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
            sumMin += (long) (maxRight[i] - i) * (i - minLeft[i]) * nums[i];
        }
        return sumMax - sumMin;
    }
}
